package com.chapter4.graph;

import java.util.Arrays;
import java.util.Stack;

import org.junit.Test;

import com.chapter4.graph.direct.Digraph;
import com.chapter4.graph.direct.DirectedBFS;
import com.chapter4.graph.direct.DirectedCycle;
import com.chapter4.graph.direct.DirectedDFS;
import com.chapter4.graph.direct.KosarajuSCC;
import com.chapter4.graph.direct.Topological;
import com.chapter4.graph.undirect.BreadthFirstSearch;
import com.chapter4.graph.undirect.CC;
import com.chapter4.graph.undirect.Graph;
import com.chapter4.graph.undirect.TwoColor;
import com.util.Constants;
import com.util.In;

/**
 * @ClassName: TestGraph
 * @Description: test
 * @author minjun minjun@bw30.com
 * @date 2015-2-25 上午1:33:18
 * 
 */
public class TestGraph {

	@Test
	public void testGraph() {
		In in = new In("F:\\算法\\attach\\tinyCG.txt");
		Graph g = new Graph(in);
		int start = 1 ;
		int dest = 5;
//		DepthFirstSearch dfs = new DepthFirstSearch(g, start);
//		dfs.printEdgeArray();
		BreadthFirstSearch bfs=new BreadthFirstSearch(g, start);
		Stack<Integer> path = (Stack<Integer>) bfs.pathTo(dest);
		StringBuilder sb = new StringBuilder();
		while (!path.isEmpty()) {
			sb.append(path.pop() + "->");
		}
		int len = sb.toString().length();

		if (sb.toString().endsWith("->"))
			sb.delete(len - 2, len);

		System.out.println(sb.toString());
	}
	
	@Test
	public void testCC(){
		In in = new In("F:\\算法\\attach\\tinyG.txt");
		Graph g = new Graph(in);
		CC cc=new CC(g);
		int v=5,w=6;
		System.out.println(cc.count()+"个子图");
		System.out.println(v+"和"+w+(cc.connected(v,w)?"连通":"不连通"));
		cc.printComponents();
	}
	
	boolean a;
	
	boolean[] aa=new boolean[3];
	
	@Test
	public void a(){
		System.out.println(a);
		System.out.println(Arrays.toString(aa));
	}
	
	@Test
	public void testTwoColor(){
		In in = new In("F:\\算法\\attach\\twocolor.txt");
		Graph g = new Graph(in);
		
		TwoColor t=new TwoColor(g);
		System.out.println(t.isBipartite());
	}
	
	@Test
	public void testDigraph(){
		In in=new In("F:\\算法\\attach\\tinyDG.txt");
		Digraph d=new Digraph(in);
		
		System.out.println(d);
		System.out.println("------------");
		System.out.println(d.reverse());
	}
	
	@Test
	public void testDirectedDFS(){
		In in=new In("F:\\算法\\attach\\tinyDG.txt");
		Digraph d=new Digraph(in);
		int s=0;
		int v=5;
		DirectedDFS dfs=new DirectedDFS(d, s);
		System.out.println(dfs.hasPathTo(v));
		System.out.println("-------------");
		System.out.println(dfs.path(v));
	}
	
	@Test
	public void testDirectedBFS(){
		In in=new In("F:\\算法\\attach\\tinyDG.txt");
		Digraph d=new Digraph(in);
		int s=0;
		int v=4;
		DirectedBFS bfs=new DirectedBFS(d, s);
		System.out.println(bfs.hasPathTo(v));
		System.out.println("-------------");
		System.out.println(bfs.path(v));
	}
	
	@Test
	public void testDirectedCycle(){
		In in=new In("F:\\算法\\attach\\tinyDG.txt");
		Digraph d=new Digraph(in);
		DirectedCycle dc=new DirectedCycle(d);
		System.out.println(dc.hasCycle());
		Stack<Integer> cycle=(Stack<Integer>) dc.cycle();
		while(!cycle.isEmpty()){
			System.out.print(cycle.pop()+"->");
		}
	}
	
	@Test
	public void testStronglyCC(){
		In in=new In("F:\\算法\\attach\\tinyDG.txt");
		Digraph d=new Digraph(in);
		KosarajuSCC k=new KosarajuSCC(d);
		int count=k.count();
		int len=d.V();
		for(int i=0;i<count;i++){
			for(int j=0;j<len;j++){
				if(k.id(j)==i)
					System.out.print(j+"\t");
			}
			System.out.println();
		}
	}
	
	@Test
	public void testTop(){
		In in = new In(Constants.dirPath + "tinyEWD.txt");
		Digraph g = new Digraph(in);
		Topological top=new Topological(g);
		
		Stack<Integer> topOrder=(Stack<Integer>) top.reversePost();
		while(!topOrder.isEmpty()){
			System.out.print(topOrder.pop()+" ");
		}
	}
}
